package com.waiting.leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/7
 **/
public class RestoreIPAddresses93 {

    static List<String> result = new LinkedList<>();

    public static void main(String[] args) {
        String s = "0000";
        restoreIpAddresses(s);
        for (String item : result) {
            System.out.println(item);
        }
    }

    public static List<String> restoreIpAddresses(String s) {
        ite(s, 0, 4, new StringBuilder());
        return result;
    }


    public static void ite(String s, int start, int target, StringBuilder stringBuilder) {
        if (target == 1) {
            String tmp = s.substring(start);
            if (judge(tmp)) {
                stringBuilder.append(tmp);
                result.add(stringBuilder.toString());
            }
            return;
        }
        //继续迭代
        //取一位
        String tmp = "";
        if (start + 1 < s.length()) {
            tmp = s.substring(start, start + 1);
            if (judge(tmp)) {
                StringBuilder oneSb = new StringBuilder(stringBuilder);
                oneSb.append(tmp);
                oneSb.append(".");
                ite(s, start + 1, target - 1, oneSb);
            }
        }

        //取两位
        if ((start + 2) < s.length()) {
            tmp = s.substring(start, start + 2);
            if (judge(tmp)) {
                StringBuilder oneSb = new StringBuilder(stringBuilder);
                oneSb.append(tmp);
                oneSb.append(".");
                ite(s, start + 2, target - 1, oneSb);
            }
        }

        //取三位
        if ((start + 3) < s.length()) {
            tmp = s.substring(start, start + 3);
            if (judge(tmp)) {
                StringBuilder oneSb = new StringBuilder(stringBuilder);
                oneSb.append(tmp);
                oneSb.append(".");
                ite(s, start + 3, target - 1, oneSb);
            }
        }
    }

    //判断是否满足ipv4的要求
    public static boolean judge(String s) {
        if (s.isEmpty()) {
            return false;
        }
        if (s.charAt(0) == '0' && s.length() != 1) {
            return false;
        }
        Double value = Double.valueOf(s);
        return value > 255 ? false : true;
    }
}
